Entropy coding delivers lossless compression at the last stage of video encoding (and first stage of video decoding), after the video has been reduced to a series of syntax elements. Arithmetic coding is a type of entropy coding that can achieve compression close to the entropy of a sequence by effectively mapping the symbols (i.e., syntax elements) to codewords with a non-integer number of bits. In H.264/AVC, the CABAC provides a 9 to 14% improvement over the Huffman-based Context-based Adaptive Variable Length Coding (CAVLC).
CABAC involves three main functions: binarization, context modeling, and arithmetic coding. Binarization maps syntax elements to binary symbols (bins). Context modeling estimates the probability of the bins, and arithmetic coding compresses the bins.
Arithmetic coding is based on recursive interval division. Binary arithmetic coding refers to the case where the alphabet of the symbol is restricted to zero and one (i.e., binary symbols (bins)). The size of the subintervals is determined by multiplying the current interval by the probabilities of the bin. At the encoder, a subinterval is selected based on the value of the bin. The range and lower bound of the interval are updated after every selection. At the decoder, the value of the bin depends on the location of the offset. The offset is a binary fraction described by the encoded bits received at the decoder. The range and lower bound of the current interval have limited bit-precision, so renormalization is required whenever the range falls below a certain value to prevent underflow.
FIG. 1A is a schematic diagram illustrating a general structure of a CABAC engine 500. As shown by FIG. 1A, the CABAC engine 500 contains an arithmetic decoder 502, a debinarizer 504, and a context modeling unit 506, having a context memory and a context selection unit therein.
A flowchart of a presently known arithmetic decoder is shown in FIG. 1B. The range, offset, and the selected context, described by its current state and most probable symbol (MPS), and inputs to block 4. In block 4, the size of the subintervals is calculated; specifically, the range of the least probable symbol (rLPS), and the range of the most probable symbol (rMPS).
The CABAC engine used in H.264/AVC leverages a modulo coder (M coder) to calculate the range of a subinterval based on the product of the current range and the probability of the bin. The M coder involves using a look up table (LUT) rather than a true multiplier to reduce implementation complexity. In block 4, the 6-bit context state and two bits from the range are used as input to a look up table (LUT) in order to determine the rLPS. The rMPS is then determined by subtracting the rLPS from the range. rMPS is then passed to block 6, where rMPS is compared to the offset.
In block 6, if offset is greater than or equal to rMPS, then the next block is 8, where the decoded bin is determined to be not equal MPS, or in other words equal to least probable symbol (LPS). In block 8, the offset value is also updated by subtracting rMPS from it, and the range is updated by setting it equal to rLPS. After block 8, the next block is 12 where the state is compared to 0. If the state is equal to zero, then the next block is 14 where the MPS value is updated to equal 1 minus MPS (i.e., the values of MPS and LPS are swapped). After block 14, the next step is 16. If in block 12, state is not equal to 0, then the next step is directly to block 16. In block 16, the state is updated using a 64×1 LUT.
In block 6, if offset is not greater than or equal to rMPS, then the next block is 10, where the decoded bin is determined to be equal to MPS, the range is updated to be equal to rLPS, the state is updated using a 64×1 LUT. The MPS value is not updated.
The next step for both block 10 and 16 is block 18. The updated range and offsets are renormalized. Renormalization involves determining the number of leading zeros in the updated range value and shifting to the left. The updated offset is shifted by the same amount. The output of block 18 is the renormalized range and offset; the updated state and MPS are also the output of the binary arithmetic decoder.
The arithmetic coding engine typically contains the critical path in H.264/AVC CABAC. Unfortunately, there are delays in the critical path.
In order to achieve optimal compression efficiency, an accurate probability must be used to code each bin. For High profile in H.264/AVC, CABAC uses over 400 different probability models to achieve the significant coding gains over CAVLC. All bins of the same type (i.e., with the same probability distribution and characteristics) are grouped together in a context and use the same model. Accordingly, the context of a bin dictates the probability with which it is coded.
Since distributions in neighboring macroblocks are correlated, the value of the syntax elements of the macroblocks (or blocks) located to the top and left impact the context selection. For instance, bins of motion vector difference (mvd) syntax elements that have neighbors with large mvds, use the same context. Unfortunately, using information from the top and left neighbor requires additional memory, which adds to area cost of context modeling.
Thus, a heretofore unaddressed need exists in the industry to address the aforementioned deficiencies and inadequacies.